任务调度——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

一、单机任务调度

问题描述：

• 我们现有许多演讲要在阶梯教室中举行。每一个演讲都可以用唯一的起始和终止时间来确定，如果两个演讲时间有部分或全部重复，那么它们是无法同时在阶级教室中举行的。现在我们想要尽最大可能的利用这个教室，让演讲数量最大化。我们假设在某一演讲结束的瞬间我们就可以立即开始另一个演讲。

算法解析：

1. 按结束时间升序排序
2. 第一个活动必选
3. 遍历当前活动开始时间 >= 上一个活动结束时间

#include <iostream>
#include <vector>
using namespace std;

// 活动结构体：开始时间、结束时间、演讲编号
struct Activity {
    int start;
    int end;
    int id;
};

// 按结束时间升序排序
bool compareActivity(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

// 活动选择：返回选中的活动编号
vector<int> activitySelection(vector<Activity>& activities) {
    sort(activities.begin(), activities.end(), compareActivity);
    vector<int> selected;
    // 第一个活动必选
    selected.push_back(activities[0].id);
    int lastEnd = activities[0].end;

    for (int i = 1; i < activities.size(); ++i) {
        // 当前活动开始时间 >= 上一个活动结束时间，无冲突
        if (activities[i].start >= lastEnd) {
            selected.push_back(activities[i].id);
            lastEnd = activities[i].end;
        }
    }
    return selected;
}

int main() {
    // 测试：6个活动，格式(start, end, id)
    vector<Activity> acts = {{1,4,1}, {3,5,2}, {0,6,3}, {5,7,4}, {3,8,5}, {7,9,6}};
    vector<int> res = activitySelection(acts);
    cout << "选中的活动编号：";
    for (int id : res) cout << id << " ";

    return 0;
} 
        

输出结果

输出：1 4 6
        

二、多机任务调度

问题描述：

• 有n个人排队到r个水龙头去打水，他们装满水桶的时间为t1,t2,...tn为整数且各不相等，应如何安排他们的打水顺序才能使他们花费的时间最少（含等待时间）？
• 输入格式:
  1. 第一行两个整数 n,r。
  2. 接下来 N 行，每行一个整数 t_i。
• 输出格式:
  1. 一个整数表示答案

算法解析：

核心思路是短任务优先分配，结合水龙头的空闲状态动态调度，最终实现总耗时最优。

1. 将所有人的打水时间按升序排序（短时间在前，长时间在后）；
2. 将排序后的打水任务依次分配给当前空闲的水龙头，若所有水龙头都在工作，则分配给当前总累积耗时最少的水龙头（即最早能空闲的水龙头）；
3. 每个水龙头的累积耗时 = 原有累积耗时 + 新分配人员的打水时间（该值为该人员在该水龙头的实际总耗时：等待时间 + 自身打水时间）。

举例验证：

场景：n=5 人，打水时间[5,3,1,4,2]，r=2 个水龙头。

1. 排序打水时间：[1,2,3,4,5]；
2. 分配过程：
   • 水龙头 1：分配 1 → 累积耗时 1；水龙头 2：分配 2 → 累积耗时 2（当前水龙头 1 更早空闲）；
   • 水龙头 1：分配 3 → 累积耗时 1+3=4；水龙头 2：分配 4 → 累积耗时 2+4=6（当前水龙头 1 更早空闲）；
   • 水龙头 1：分配 5 → 累积耗时 4+5=9；
3. 所有人的耗时分别为：1、2、4、6、9；
4. 总耗时之和=1+2+4+6+9=22（为最优解，若打乱顺序，总耗时会显著增加）。

若反序分配（长时间优先）：排序[5,4,3,2,1]，总耗时之和 = 5+4+8+6+9=32，远大于最优解。

#include <iostream>
#include <vector>

using namespace std;

// 计算打水最小总耗时（总耗时=所有人的打水+等待时间之和）
// 参数：t - 原始打水时间数组，r - 水龙头数量
long long minTotalWaterTime(vector<int>& t, int r) {
    int n = t.size();
    // 边界情况：无人员或无水龙头
    if (n == 0) return 0;
    if (r <= 0) return LLONG_MAX;

    // 步骤1：将打水时间升序排序（短任务优先）
    sort(t.begin(), t.end());

    // 步骤2：初始化
    vector<long long> tap_times(r, 0);// 记录任务时间
    vector<vector<int>> tap_tasks(r);// 记录水龙头分配的任务
    vector<vector<int>> tap_wait(r);// 记录等待时间
    long long total_time = 0; //记录总耗时

    // 步骤3：遍历排序后的打水时间，依次分配给最早空闲的水龙头
    for (int time : t) {
        // 找到当前累积耗时最小的水龙头索引
        int min_idx = 0;
        for (int i = 1; i < r; ++i) {
            if (tap_times[i] < tap_times[min_idx]) {
                min_idx = i;
            }
        }
        // 分配任务，更新水龙头累积耗时
        tap_times[min_idx] += time;
        tap_tasks[min_idx].push_back(time);
    }
    // 打印调度结果
    cout << "==================== 水龙头调度分配结果 ====================" << endl;
    for (int i = 0; i < r; ++i) {
        cout << "水龙头" << i+1 << "：分配任务[";
        int tasks_time = 0;// 记录任务耗时
        for (int j = 0; j < tap_tasks[i].size(); ++j) {
            if (j > 0) cout << ", ";
            cout << tap_tasks[i][j];
            tasks_time += tap_tasks[i][j];
        }
        cout << "] | 任务耗时：" << tasks_time << "ms" << endl;
    }
    cout << "============================================================" << endl;

    // 步骤4：计算任务等待时间
    for (int i = 0; i < r; ++i) {
        tap_wait[i].push_back(0);//每个水龙头的第一个任务微等待时间为0
        for(int j = 1; j < tap_tasks[i].size(); ++j)
        {
            tap_wait[i].push_back(tap_tasks[i][j-1] + tap_wait[i][j-1]);//当前任务等待时间 = 上一个任务等待时间 + 上一个任务时间
        }
    }
    // 打印任务等待耗时结果
    cout << "==================== 任务等待耗时结果 ====================" << endl;
    for (int i = 0; i < r; ++i) {
        cout << "水龙头" << i+1 << "：任务等待[";
        int total_wait = 0;
        for (int j = 0; j < tap_tasks[i].size(); ++j) {
            if (j > 0) cout << ", ";
            cout << tap_wait[i][j] ;
            total_wait += tap_wait[i][j] ;
        }
        cout << "] | 等待耗时：" << total_wait << "ms" << endl;
    }
    cout << "============================================================" << endl;

    // // 步骤5：计算任务总耗时
    cout << "==================== 任务总耗时结果 ====================" << endl;
    for (int i = 0; i < r; ++i) {
        long long sum_time = 0;
        cout << "水龙头" << i+1 << "：任务总耗时[";
        for (int j = 0; j < tap_tasks[i].size(); ++j) {
            if (j > 0) cout << ", ";
            sum_time = sum_time + tap_tasks[i][j] + tap_wait[i][j];
            cout << tap_tasks[i][j] << "+" << tap_wait[i][j] << "=" << tap_tasks[i][j] + tap_wait[i][j];
        }
        total_time += sum_time; // 步骤4：计算总耗时（所有水龙头累积耗时之和）
        cout << "] | 总耗时：" << sum_time << "ms" << endl;
    }
    cout << "============================================================" << endl;

    return total_time;
}

int main() {
    // 输入：人数n、水龙头数r
    int n, r;
    cout << "请输入打水人数n：";
    cin >> n;
    cout << "请输入水龙头数量r：";
    cin >> r;

    // 输入：n个人的打水时间（互不相等的正整数）
    vector<int> t(n);
    cout << "请输入" << n << "个人的打水时间（空格分隔，互不相等正整数）：";
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }

    // 计算最小总耗时
    long long min_total = minTotalWaterTime(t, r);

    // 输出结果
    cout << "所有人打水的最小总花费时间（打水+等待）：" << min_total << "ms" << endl;

    return 0;
}
        

输出结果

请输入打水人数n：5
请输入水龙头数量r：2
请输入5个人的打水时间（空格分隔，互不相等正整数）：1 2 3 4 5
==================== 水龙头调度分配结果 ====================
水龙头1：分配任务[1, 3, 5] | 任务耗时：9ms
水龙头2：分配任务[2, 4] | 任务耗时：6ms
============================================================
==================== 任务等待耗时结果 ====================
水龙头1：任务等待[0, 1, 4] | 等待耗时：5ms
水龙头2：任务等待[0, 2] | 等待耗时：2ms
============================================================
==================== 任务总耗时结果 ====================
水龙头1：任务总耗时[1+0=1, 3+1=4, 5+4=9] | 总耗时：14ms
水龙头2：任务总耗时[2+0=2, 4+2=6] | 总耗时：8ms
============================================================
所有人打水的最小总花费时间（打水+等待）：22ms